/*
 * @Author: szx
 * @Date: 2022-01-13 13:24:27
 * @LastEditTime: 2022-01-13 13:32:27
 * @Description:
 * @FilePath: \leetcode\1000-1099\1049\1049.js
 */
/**
 * @param {number[]} stones
 * @return {number}
 */

var lastStoneWeightII = function (stones) {
    const sum = stones.reduce((prev, curr) => prev + curr);
    if (sum & 1) return false;
    const target = Math.floor(sum / 2);
    const dp = new Array(target + 1).fill(0);
    for (let i = 0; i < stones.length; i++) {
        for (let j = target; j >= stones[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }
    return sum - dp[target] * 2;
};
